<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>jump</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="jump">jump</h1>
<h1 id="1-tushare-roy-minimum-jump-to-reach-end">1. Tushare Roy, Minimum jump to reach end</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=cETfFsSTGJI&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=21">https://www.youtube.com/watch?v=cETfFsSTGJI&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=21</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MinJumpToReachEnd.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MinJumpToReachEnd.java</a></li>
</ul>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp13a.png" alt="dp13a.png"></p>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp13b.png" alt="dp13b.png"></p>
<p>时间复杂度应该是 O(n^2) 空间复杂度O(n)</p>
<pre><code class="language-java"><div>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">minJump</span><span class="hljs-params">(<span class="hljs-keyword">int</span> arr[],<span class="hljs-keyword">int</span> result[])</span></span>{
        
        <span class="hljs-keyword">int</span> []jump = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[arr.length];
        jump[<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>; i &lt; arr.length ; i++){
            jump[i] = Integer.MAX_VALUE-<span class="hljs-number">1</span>;
        }
        
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>; i &lt; arr.length; i++){
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>; j &lt; i; j++){
                <span class="hljs-keyword">if</span>(arr[j] + j &gt;= i){
                    <span class="hljs-keyword">if</span>(jump[i] &gt; jump[j] + <span class="hljs-number">1</span>){
                        result[i] = j;
                        jump[i] = jump[j] + <span class="hljs-number">1</span>;
                    }
                }
            }
        }
        
        <span class="hljs-keyword">return</span> jump[jump.length-<span class="hljs-number">1</span>];
    }
</div></code></pre>
<p>tushare roy的这个视频对应着 leetcode 45. Jump Game II 到达末尾的次数最少.</p>
<h1 id="2-leetcode">2. leetcode</h1>
<h2 id="21-55-jump-game-能否到达末尾">2.1 55. Jump Game  能否到达末尾</h2>
<ul>
<li><a href="https://leetcode.com/problems/jump-game/">https://leetcode.com/problems/jump-game/</a></li>
</ul>
<p>我的while答案, 比较繁琐</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canJump</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; bool:</span>
        n = len(nums)
        <span class="hljs-keyword">if</span> n &lt;= <span class="hljs-number">1</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        
        cur = <span class="hljs-number">0</span>
        right = <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> cur &lt; n:

            right2 = right
            <span class="hljs-keyword">while</span> cur &lt;= right:
                right2 = max(right2, cur + nums[cur])
                cur += <span class="hljs-number">1</span>
            <span class="hljs-comment">#print(f"{cur} {right} {right2}")</span>
            <span class="hljs-keyword">if</span> right2 &gt;= n<span class="hljs-number">-1</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">if</span> right2 &lt;= right:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
            right = right2
            
        <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
    
</div></code></pre>
<p>讨论区的答案1</p>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canJump</span><span class="hljs-params">(self, nums)</span>:</span>
    m = <span class="hljs-number">0</span>
    <span class="hljs-keyword">for</span> i, n <span class="hljs-keyword">in</span> enumerate(nums):
        <span class="hljs-keyword">if</span> i &gt; m:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        m = max(m, i+n)
    <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
</div></code></pre>
<p>讨论区的答案2, 结合下面45 Jump II 的答案，添加一个判断即可. &lt;== <strong>推荐算法</strong></p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canJump</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; bool:</span>
        n = len(nums)
        right = <span class="hljs-number">0</span>
        right_total = <span class="hljs-number">0</span>
        step = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">if</span> i &gt; right_total:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
            <span class="hljs-keyword">if</span> i &gt; right:
                step += <span class="hljs-number">1</span>
                right = right_total
            right_total = max(right_total, i+nums[i])
        <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
</div></code></pre>
<p>tushare roy的算法, 应该是对的，但是会超时。。。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canJump</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; bool:</span>
        n = len(nums)
        dp = [<span class="hljs-number">0</span>] + [<span class="hljs-number">100000</span>] * (n<span class="hljs-number">-1</span>)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i):
                <span class="hljs-keyword">if</span> j + nums[j] &gt;= i:
                    dp[i] = min(dp[i], dp[j] + <span class="hljs-number">1</span>)
        <span class="hljs-comment">#print(dp)</span>
        <span class="hljs-keyword">return</span> dp[n<span class="hljs-number">-1</span>] != <span class="hljs-number">100000</span>
</div></code></pre>
<h2 id="22-45-jump-game-ii-到达末尾的次数最少">2.2 45. Jump Game II 到达末尾的次数最少</h2>
<ul>
<li><a href="https://leetcode.com/problems/jump-game-ii/">https://leetcode.com/problems/jump-game-ii/</a></li>
</ul>
<p>我的算法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">jump</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>        
        <span class="hljs-comment"># solution 2, O(n)</span>
        n = len(nums)
        step = <span class="hljs-number">0</span>
        total_right = <span class="hljs-number">0</span>
        step_right = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>):  <span class="hljs-comment"># 这里很关键,不是 range(n)</span>
            total_right = max(i+nums[i], total_right)
            <span class="hljs-keyword">if</span> i == step_right:
                step += <span class="hljs-number">1</span>
                step_right = total_right
        <span class="hljs-keyword">return</span> step
</div></code></pre>
<p>或者我的while算法，感觉不太好...</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">jump</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>        
        <span class="hljs-comment"># solution 2, O(n)</span>
        n = len(nums)
        step = <span class="hljs-number">0</span>
        right = <span class="hljs-number">0</span>
        i = <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> i &lt; n<span class="hljs-number">-1</span>:
            right2 = right
            <span class="hljs-keyword">while</span> i &lt;= right:
                right2 = max(right2, i + nums[i])
                i += <span class="hljs-number">1</span>
            step += <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> right2 &gt;= n<span class="hljs-number">-1</span>:
                <span class="hljs-keyword">return</span> step
            right = right2
        <span class="hljs-keyword">return</span> step
</div></code></pre>
<p>社区的答案 &lt;== <strong>推荐算法</strong></p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">jump</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        n = len(nums)
        right = <span class="hljs-number">0</span>
        right_total = <span class="hljs-number">0</span>
        step = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">if</span> i &gt; right:
                step += <span class="hljs-number">1</span>
                right = right_total
            right_total = max(right_total, i+nums[i])
        <span class="hljs-keyword">return</span> step
    
</div></code></pre>
<p>tushare roy 算法, timeout</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">jump</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        <span class="hljs-comment"># solution 1, time out   O(n^2)</span>
        right = <span class="hljs-number">0</span>
        n = len(nums)
        dp = [float(<span class="hljs-string">'inf'</span>)] * n
        dp[<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i,num <span class="hljs-keyword">in</span> enumerate(nums):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i):
                <span class="hljs-keyword">if</span> nums[j] + j &gt;= i:
                    dp[i] = min(dp[i], dp[j]+<span class="hljs-number">1</span>)
        <span class="hljs-keyword">return</span> dp[n<span class="hljs-number">-1</span>]
</div></code></pre>
<p>也可以考虑用bfs方式来遍历, 尝试写了一下，效率不高，还是放弃了。 主要是这种range jump的方式，对下一节点不好处理。</p>
<h2 id="23-1306-jump-game-iii-exact-jump-to-any-index-with-value-0-not-range-jump">2.3 1306. Jump Game III. exact &quot;jump to any index with value 0&quot;, not range jump</h2>
<ul>
<li><a href="https://leetcode.com/problems/jump-game-iii/">https://leetcode.com/problems/jump-game-iii/</a></li>
<li>这道题就是既可以往左跳，或者往右跳，</li>
<li>但是在i处只能跳精确的nums[i]步，而不是 1~nums[i]步</li>
<li>并且指定了初始位置start， 不是固定从0开始跳了。</li>
<li>关于&quot;jump to any index with value 0&quot; 的理解。
<ul>
<li>如果arr = [0,4,2,3,0,3,1,2], 里面有2个0, 只要从start开始，能跳到任何一个0，就返回True, 否则返回False</li>
</ul>
</li>
</ul>
<p>我的暴力解法，会超时. O(n^2)</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canReach</span><span class="hljs-params">(self, arr: List[int], start: int)</span> -&gt; bool:</span>
        n = len(arr)
        dp = [<span class="hljs-number">0</span>] * n
        dp[start] = <span class="hljs-number">1</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n):
                <span class="hljs-keyword">if</span> dp[j] == <span class="hljs-number">0</span>:
                    <span class="hljs-keyword">continue</span>
                <span class="hljs-keyword">if</span> j - arr[j] &gt;= <span class="hljs-number">0</span>:
                    dp[j - arr[j]] = <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> j + arr[j] &lt; n: 
                    dp[j+arr[j]] = <span class="hljs-number">1</span>
                    
            <span class="hljs-comment">#print(dp)</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">if</span> arr[i] == <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> dp[i] == <span class="hljs-number">1</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
    
</div></code></pre>
<p>本题本质上是图的遍历，下面用dfs解法, 时间复杂度O(n), 每个元素只遍历一次</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canReach</span><span class="hljs-params">(self, arr: List[int], start: int)</span> -&gt; bool:</span>
        n = len(arr)
        stack = [start]
        visited = [<span class="hljs-number">0</span>] * n
        <span class="hljs-keyword">while</span> stack:
            node = stack.pop()
            <span class="hljs-keyword">if</span> visited[node]:
                <span class="hljs-keyword">continue</span>
            visited[node] = <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> arr[node] == <span class="hljs-number">0</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">if</span> node - arr[node] &gt;= <span class="hljs-number">0</span>:
                stack.append(node-arr[node])
            <span class="hljs-keyword">if</span> node + arr[node] &lt; n:
                stack.append(node+arr[node])
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
    
</div></code></pre>
<p>本题有dp解法么？ 好像没有啊. 讨论区里面都是dfs解法。</p>
<h2 id="24-1345-jump-game-iv">2.4 1345. Jump Game IV</h2>
<ul>
<li><a href="https://leetcode.com/problems/jump-game-iv/">https://leetcode.com/problems/jump-game-iv/</a></li>
</ul>
<p>In one step you can jump from index i to index:</p>
<ul>
<li>i + 1 where: i + 1 &lt; arr.length.</li>
<li>i - 1 where: i - 1 &gt;= 0.</li>
<li>j where: arr[i] == arr[j] and i != j.</li>
<li>Return the minimum number of steps to reach the last index of the array.</li>
<li>Notice that you can not jump outside of the array at any time.</li>
</ul>
<p>跳跃有3种类型</p>
<ul>
<li>往左跳一步</li>
<li>往右跳一步</li>
<li>跳到value相同的任意位置</li>
</ul>
<p>我首先想到的BFS算法， 会超时</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minJumps</span><span class="hljs-params">(self, arr: List[int])</span> -&gt; int:</span>
        d = defaultdict(list)
        <span class="hljs-keyword">for</span> i,num <span class="hljs-keyword">in</span> enumerate(arr):
            d[num].append(i)
            
        n = len(arr)
        stack = [<span class="hljs-number">0</span>]
        visited = [<span class="hljs-number">0</span>] * n
        visited[<span class="hljs-number">0</span>] = <span class="hljs-number">1</span>
        step = <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> stack:
            stack2 = []
            <span class="hljs-keyword">while</span> stack:
                node = stack.pop()
                <span class="hljs-keyword">if</span> node == n<span class="hljs-number">-1</span>:
                    <span class="hljs-keyword">return</span> step
                node2 = node - <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> node2 &gt;= <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> visited[node2] == <span class="hljs-number">0</span>:
                    stack2.append(node2)
                    visited[node2] = <span class="hljs-number">1</span>
                node2 = node + <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> node2 &lt; n <span class="hljs-keyword">and</span> visited[node2] == <span class="hljs-number">0</span>:
                    stack2.append(node2)
                    visited[node2] = <span class="hljs-number">1</span>
                    
                <span class="hljs-keyword">for</span> node2 <span class="hljs-keyword">in</span> d[arr[node]]:
                    <span class="hljs-keyword">if</span> visited[node2] == <span class="hljs-number">0</span>:
                        stack2.append(node2)
                        visited[node2] = <span class="hljs-number">1</span>
                        
            stack = stack2    
            step += <span class="hljs-number">1</span>
        <span class="hljs-keyword">return</span> step 
</div></code></pre>
<p>上面的代码会超时，是遇到了一种测试用例 [7,7,7,7...7,7,11], 如果有5000个7就会超时。下面用一种预处理去除的办法来解决</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minJumps</span><span class="hljs-params">(self, arr: List[int])</span> -&gt; int:</span>
        
        arr = self.remove_duplicated(arr)
        
        d = defaultdict(list)
        <span class="hljs-keyword">for</span> i,num <span class="hljs-keyword">in</span> enumerate(arr):
            d[num].append(i)
            
        n = len(arr)
        stack = [<span class="hljs-number">0</span>]
        visited = [<span class="hljs-number">0</span>] * n
        visited[<span class="hljs-number">0</span>] = <span class="hljs-number">1</span>
        step = <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> stack:
            stack2 = []
            <span class="hljs-keyword">while</span> stack:
                node = stack.pop()
                <span class="hljs-keyword">if</span> node == n<span class="hljs-number">-1</span>:
                    <span class="hljs-keyword">return</span> step
                node2 = node - <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> node2 &gt;= <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> visited[node2] == <span class="hljs-number">0</span>:
                    stack2.append(node2)
                    visited[node2] = <span class="hljs-number">1</span>
                node2 = node + <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> node2 &lt; n <span class="hljs-keyword">and</span> visited[node2] == <span class="hljs-number">0</span>:
                    stack2.append(node2)
                    visited[node2] = <span class="hljs-number">1</span>
                    
                <span class="hljs-keyword">for</span> node2 <span class="hljs-keyword">in</span> d[arr[node]]:
                    <span class="hljs-keyword">if</span> visited[node2] == <span class="hljs-number">0</span>:
                        stack2.append(node2)
                        visited[node2] = <span class="hljs-number">1</span>
                        
            stack = stack2    
            step += <span class="hljs-number">1</span>
        <span class="hljs-keyword">return</span> step
    
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">remove_duplicated</span><span class="hljs-params">(self, arr)</span>:</span>
        n = len(arr)
        <span class="hljs-keyword">if</span> n &lt;= <span class="hljs-number">1</span>:
            <span class="hljs-keyword">return</span> arr
        ans = []
        i = <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> i &lt; n:  <span class="hljs-comment"># 注意，这里的处理必须是 arr[i] == arr[i+1]  == arr[i+2] 连续3个相等，才能去重。</span>
            <span class="hljs-keyword">while</span> i&lt;n<span class="hljs-number">-2</span> <span class="hljs-keyword">and</span> arr[i] == arr[i+<span class="hljs-number">1</span>] <span class="hljs-keyword">and</span> arr[i] == arr[i+<span class="hljs-number">2</span>]:
                i += <span class="hljs-number">1</span>
            ans.append(arr[i])
            i += <span class="hljs-number">1</span>        
        <span class="hljs-keyword">return</span> ans  
        
</div></code></pre>
<p>看了社区的答案，基本都是BFS, 只是一些细节处理的可能不一样。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minJumps</span><span class="hljs-params">(self, arr: List[int])</span> -&gt; int:</span>
        
        <span class="hljs-comment"># if there is no dups</span>
        <span class="hljs-keyword">if</span> len(set(arr)) == len(arr):
            <span class="hljs-keyword">return</span> len(arr)<span class="hljs-number">-1</span>
        
        conn = collections.defaultdict(set)
        <span class="hljs-keyword">for</span> i, x <span class="hljs-keyword">in</span> enumerate(arr):
            conn[x].add(i)
            
        res, seen, visit = <span class="hljs-number">0</span>, {<span class="hljs-number">0</span>}, set()
        
        <span class="hljs-keyword">while</span> len(arr)<span class="hljs-number">-1</span> <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> seen:
            res += <span class="hljs-number">1</span>
            tmp = set()
            
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> seen:
                <span class="hljs-keyword">if</span> i<span class="hljs-number">-1</span> &gt; <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> i<span class="hljs-number">-1</span> <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> seen: tmp.add(i<span class="hljs-number">-1</span>)
                <span class="hljs-keyword">if</span> i+<span class="hljs-number">1</span> &lt; len(arr) <span class="hljs-keyword">and</span> i +<span class="hljs-number">1</span> <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> seen: tmp.add(i+<span class="hljs-number">1</span>)
                    
                <span class="hljs-keyword">if</span> arr[i] <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> visit:
                    tmp |= (conn[arr[i]] - seen)
                    visit.add(arr[i])
                
            tmp -= seen
            seen |= tmp
      
            
        <span class="hljs-keyword">return</span> res
</div></code></pre>
<h2 id="25-1340-jump-game-v">2.5 1340. Jump Game V</h2>
<ul>
<li><a href="https://leetcode.com/problems/jump-game-v/">https://leetcode.com/problems/jump-game-v/</a></li>
</ul>
<h3 id="251-my-solution-1">2.5.1 my solution 1</h3>
<p>Given an array of integers arr and an integer d. In one step you can jump from index i to index:</p>
<ul>
<li>i + x where: i + x &lt; arr.length and 0 &lt; x &lt;= d.</li>
<li>i - x where: i - x &gt;= 0 and 0 &lt; x &lt;= d.</li>
<li>In addition, you can only jump from index i to index j if arr[i] &gt; arr[j] and arr[i] &gt; arr[k] for all indices k between i and j (More formally min(i, j) &lt; k &lt; max(i, j)).</li>
</ul>
<p>You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.</p>
<p>Notice that you can not jump outside of the array at any time.</p>
<p>最开始的想法，就是先通过_check()把arr转换为tree, 然后通过_bfs从每个tree的root开始遍历，得到tree的最大深度。 时间复杂度应该是O(k*n), 提交后会超时</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict
<span class="hljs-keyword">from</span> pprint <span class="hljs-keyword">import</span> pprint

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxJumps</span><span class="hljs-params">(self, arr: List[int], d: int)</span> -&gt; int:</span>
        <span class="hljs-comment"># construct the trees</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_check</span><span class="hljs-params">(i, dd, n, is_roots)</span>:</span>
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, d+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">if</span> i+j &lt; n <span class="hljs-keyword">and</span> arr[i+j] &lt; arr[i]:
                    dd[i].append(i+j)
                    is_roots[i+j] = <span class="hljs-number">0</span>
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
            
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, d+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">if</span> i-j &gt;= <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> arr[i-j] &lt; arr[i]:
                    dd[i].append(i-j)
                    is_roots[i-j] = <span class="hljs-number">0</span>
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
                    
        <span class="hljs-comment"># bfs loop the trees from root</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_bfs</span><span class="hljs-params">(i, dd, level)</span>:</span>
            <span class="hljs-keyword">if</span> len(dd[i]) == <span class="hljs-number">0</span>:
                self.ans = max(self.ans, level)
                <span class="hljs-keyword">return</span>
            <span class="hljs-keyword">for</span> node <span class="hljs-keyword">in</span> dd[i]:
                _bfs(node, dd, level+<span class="hljs-number">1</span>)
        
        dd = defaultdict(list)
        n = len(arr)
        is_roots = [<span class="hljs-number">1</span>] * n
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            _check(i, dd, n, is_roots)
            
        self.ans = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">if</span> is_roots[i] == <span class="hljs-number">0</span>:
                <span class="hljs-keyword">continue</span>
            _bfs(i,dd,<span class="hljs-number">1</span>)
        <span class="hljs-comment">#pprint(dd)</span>
        <span class="hljs-keyword">return</span> self.ans
</div></code></pre>
<h3 id="252-my-solution-2--lru_cache">2.5.2 my solution 2, + lru_cache</h3>
<p>参考社区答案以后， 在bfs的时候，加上lru_cache就能通过了。</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict
<span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache
<span class="hljs-keyword">from</span> pprint <span class="hljs-keyword">import</span> pprint

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxJumps</span><span class="hljs-params">(self, arr: List[int], d: int)</span> -&gt; int:</span>
        dd = defaultdict(list)
        n = len(arr)
        is_roots = [<span class="hljs-number">1</span>] * n
        
        <span class="hljs-comment"># construct the trees</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_check</span><span class="hljs-params">(i, dd, n, is_roots)</span>:</span>
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, d+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">if</span> i+j &lt; n <span class="hljs-keyword">and</span> arr[i+j] &lt; arr[i]:
                    dd[i].append(i+j)
                    is_roots[i+j] = <span class="hljs-number">0</span>
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
            
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, d+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">if</span> i-j &gt;= <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> arr[i-j] &lt; arr[i]:
                    dd[i].append(i-j)
                    is_roots[i-j] = <span class="hljs-number">0</span>
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
                    
        <span class="hljs-comment"># bfs loop the trees from root</span>
<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_bfs</span><span class="hljs-params">(i)</span>:</span>
            <span class="hljs-keyword">return</span> <span class="hljs-number">1</span> + max(map(_bfs, dd[i]), default=<span class="hljs-number">0</span>)
        
       
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            _check(i, dd, n, is_roots)
            
        ans = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">if</span> is_roots[i] == <span class="hljs-number">0</span>:
                <span class="hljs-keyword">continue</span>
            ans = max(ans, _bfs(i))
        <span class="hljs-comment">#pprint(dd)</span>
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h3 id="253-lee-215-solution-1-dp">2.5.3  lee 215 solution 1 dp</h3>
<ul>
<li><a href="https://mp.weixin.qq.com/s/kEQ00_WLqDTG6tbsjQ2Xjw">https://mp.weixin.qq.com/s/kEQ00_WLqDTG6tbsjQ2Xjw</a></li>
</ul>
<p>非常短小精炼</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxJumps</span><span class="hljs-params">(self, arr: List[int], d: int)</span> -&gt; int:</span>
        n = len(arr)
        res  = [<span class="hljs-number">0</span>] * n

        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dp</span><span class="hljs-params">(i)</span>:</span>
            <span class="hljs-keyword">if</span> res[i]: <span class="hljs-keyword">return</span> res[i]
            res[i] = <span class="hljs-number">1</span>
            <span class="hljs-keyword">for</span> di <span class="hljs-keyword">in</span> [<span class="hljs-number">-1</span>, <span class="hljs-number">1</span>]:
                <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i+di, i+d*di+di, di):
                    <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> ( <span class="hljs-number">0</span>&lt;= j &lt; n <span class="hljs-keyword">and</span> arr[j] &lt; arr[i]): <span class="hljs-keyword">break</span>
                    res[i] = max(res[i], dp(j) + <span class="hljs-number">1</span>)
            <span class="hljs-keyword">return</span> res[i]

        <span class="hljs-keyword">return</span> max(map(dp, range(n)))
</div></code></pre>
<p>参考他的解法，我写出了下面的代码, 多了很多行</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxJumps</span><span class="hljs-params">(self, arr: List[int], d: int)</span> -&gt; int:</span>
        n = len(arr)
            
<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_dfs</span><span class="hljs-params">(i)</span>:</span>
            ans = <span class="hljs-number">0</span>
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i+<span class="hljs-number">1</span>, i+d+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">if</span> <span class="hljs-number">0</span> &lt;= j &lt;= n<span class="hljs-number">-1</span> <span class="hljs-keyword">and</span> arr[j] &lt; arr[i]:
                    ans = max(ans, _dfs(j))
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
                    
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i<span class="hljs-number">-1</span>, i-d<span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):
                <span class="hljs-keyword">if</span> <span class="hljs-number">0</span> &lt;= j &lt;= n<span class="hljs-number">-1</span> <span class="hljs-keyword">and</span> arr[j] &lt; arr[i]:
                    ans = max(ans, _dfs(j))
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
                    
            <span class="hljs-keyword">return</span> ans + <span class="hljs-number">1</span>
        
        maxr = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            maxr = max(maxr, _dfs(i))
        <span class="hljs-keyword">return</span> maxr
</div></code></pre>
<h3 id="254-lee215-单调栈dp-decreasing-stack--dp">2.5.4 lee215 单调栈DP Decreasing Stack + DP</h3>
<p>复杂度严格符合O(N)。 这个算法不太好懂，我暂时放弃了。</p>
<ul>
<li>Use a stack to keep the index of decreasing elements.</li>
<li>Iterate the array A. When we meet a bigger element a, we pop out the all indices j from the top of stack, where A[j] have the same value.</li>
<li>Then we update dp[i] and dp[stack[-1]].</li>
</ul>
<p>Since all indices will be pushed and popped in stack,</p>
<p>appended and iterated in L once,</p>
<p>the whole complexity is guaranteed to be O(N).</p>
<p>All element are pushed in and poped from stack1&amp;2 only once, strick O(N) time.</p>
<p>Time complexity O(N)</p>
<p>Space complexity O(N)</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxJumps</span><span class="hljs-params">(self, arr: List[int], d: int)</span> -&gt; int:</span>
        <span class="hljs-comment"># # Option1: 递归，O(nd)</span>
        <span class="hljs-comment"># count = [0] * len(arr)</span>
        <span class="hljs-comment"># res = 1</span>

        <span class="hljs-comment"># def dfs(n, count):</span>
        <span class="hljs-comment">#     if count[n]: return count[n]</span>
        <span class="hljs-comment">#     cnt = 1</span>
        <span class="hljs-comment">#     x = n+1</span>
        <span class="hljs-comment">#     # 不能用for循环，因为不允许中间出现更大的值</span>
        <span class="hljs-comment">#     while x &lt; len(arr) and x &lt;= n+d and arr[n] &gt; arr[x]:</span>
        <span class="hljs-comment">#         cnt = max(cnt, dfs(x, count) + 1)</span>
        <span class="hljs-comment">#         x+=1</span>
        <span class="hljs-comment">#     x = n-1</span>
        <span class="hljs-comment">#     while x &gt;= 0 and x &gt;= n-d and arr[n] &gt; arr[x]:</span>
        <span class="hljs-comment">#         cnt = max(cnt, dfs(x, count) + 1)</span>
        <span class="hljs-comment">#         x-=1</span>
        <span class="hljs-comment">#     count[n] = cnt</span>
        <span class="hljs-comment">#     return cnt</span>

        <span class="hljs-comment"># for j in range(len(arr)):</span>
        <span class="hljs-comment">#     res = max(res, dfs(j, count))</span>
        <span class="hljs-comment"># return res</span>


        <span class="hljs-comment"># Option 2: 单调递减栈 + DP</span>
        n = len(arr)
        dp = [<span class="hljs-number">1</span>] * (n+<span class="hljs-number">1</span>)
        stack = []
        <span class="hljs-comment"># 加上[float('inf')]是为了最后一步清空栈</span>
        <span class="hljs-keyword">for</span> i, a <span class="hljs-keyword">in</span> enumerate(arr+[float(<span class="hljs-string">'inf'</span>)]):
            <span class="hljs-comment"># 单调递减栈，更新当下和栈顶dp</span>
            <span class="hljs-keyword">while</span> stack <span class="hljs-keyword">and</span> arr[stack[<span class="hljs-number">-1</span>]] &lt; a:
                cur_l = [stack.pop()]
                <span class="hljs-comment"># 相等的元素</span>
                <span class="hljs-keyword">while</span> stack <span class="hljs-keyword">and</span> arr[stack[<span class="hljs-number">-1</span>]] == arr[cur_l[<span class="hljs-number">0</span>]]:
                    cur_l.append(stack.pop())
                <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> cur_l:
                    <span class="hljs-comment"># 更新当前位置dp</span>
                    <span class="hljs-keyword">if</span> i - j &lt;= d:
                        dp[i] = max(dp[i], dp[j]+<span class="hljs-number">1</span>)
                    <span class="hljs-comment"># 更新栈顶dp</span>
                    <span class="hljs-keyword">if</span> stack <span class="hljs-keyword">and</span> j- stack[<span class="hljs-number">-1</span>]&lt;=d:
                        dp[stack[<span class="hljs-number">-1</span>]] = max(dp[stack[<span class="hljs-number">-1</span>]], dp[j]+<span class="hljs-number">1</span>)
            stack.append(i)
        <span class="hljs-keyword">return</span> max(dp[:<span class="hljs-number">-1</span>])
</div></code></pre>

    </body>
    </html>